package binarysearch;

/**
 * 在旋转有序的数组中搜索
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 */
public class RotatedSortedArray {

    public static void main(String[] args) {
//        int[] nums = {4,5,6,0,1,2,3,4,5}; int target = 2;
        int[] nums = {1,3,5}; int target = 1;
        System.out.println(new RotatedSortedArray().search(nums, target));
    }

    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (nums[mid] == target){
                System.out.println("nums.mid 等于 target");
                return mid;
            }

            if (nums[mid] > nums[start]) {
                System.out.println("nums[mid] 大于 nums[start]");
                if (target <= nums[mid] && target >= nums[start]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else {
                System.out.println("nums[mid] 小于 nums[start]");
                if (target >= nums[mid] && target <= nums[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        if (nums[start] == target) {
            System.out.println("nums.mid = target");
            return start;
        }
        if (nums[end] == target) {
            System.out.println("nums.mid = target");
            return end;
        }
        return -1;
    }

}
